#include <iostream>
using namespace std;

template <typename T>
void qsort_helper(T *arr, int left, int right)
{
    if (left >= right) {
        return;
    }
    T &pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (arr[i] <= pivot && i < right) { i++; }
        while (arr[j] > pivot) { j--; }
        if (i < j) {
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(pivot, arr[j]);
    qsort_helper(arr, left, j-1);
    qsort_helper(arr, j+1, right);
}

template <typename T>
void qsort(T *arr, int n)
{
    qsort_helper(arr, 0, n-1);
}

int main()
{
    int a[] = { 8, 11, 3, -1, 22, 5 };
    //int a[] = { 4, 4, 4, 4 };
    int n = sizeof(a)/sizeof(a[0]);
    qsort(a, n);
    for (int i = 0; i < n; i++) {
        cout << a[i] << endl;
    }
    return 0;
}

